

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct ListNode
{
    int val;
    struct ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

typedef ListNode LNode;

 class Solution
 {
 public:
     ListNode* mergeKLists1(vector<ListNode*>& lists)
     {
         size_t sz = lists.size();

         vector<LNode*> vl;
         vl.reserve(5000);

         int flag = 0;
         for (int i = 0; i < sz; ++i)
         {
             LNode* cur = lists[i];
             while (cur)
             {
                 flag = 1;
                 vl.push_back(cur);
                 cur = cur->next;
             }
         }

         if (!flag)
             return nullptr;
         else
         {
             sort(vl.begin(), vl.end(), Less());

             LNode* prev = vl[0];
             for (int i = 1; i < vl.size(); ++i)
             {
                 prev->next = vl[i];
                 prev = vl[i];
             }
             vl[vl.size() - 1]->next = nullptr;

             return vl[0];
         }
     }

     ListNode* mergeKLists2(vector<ListNode*>& lists)
     {
         size_t sz = lists.size();
         priority_queue<LNode*, vector<LNode*>, Greater> pq;

         int flag = 0;
         for (int i = 0; i < sz; ++i)
         {
             LNode* cur = lists[i];
             while (cur)
             {
                 flag = 1;
                 pq.push(cur);
                 cur = cur->next;
             }
         }

         if (!flag)
             return nullptr;
         else
         {
             LNode* head = pq.top();
             LNode* prev = pq.top();

             pq.pop();
             while (!pq.empty())
             {
                 prev->next = pq.top();
                 prev = pq.top();
                 pq.pop();
             }
             prev->next = nullptr;

             return head;
         }
     }

     ListNode* mergeKLists3(vector<ListNode*>& lists)
     {
         size_t sz = lists.size();
         priority_queue<LNode*, vector<LNode*>, Greater> pq;

         int flag = 0;
         for (int i = 0; i < sz; ++i)
         {
             if (lists[i])
             {
                 pq.push(lists[i]);
                 flag = 1;
             }
         }

         if (!flag)
             return nullptr;
         else
         {
             LNode* head = new LNode(-1);
             LNode* prev = head;

             while (!pq.empty())
             {
                 prev->next = pq.top();
                 prev = pq.top();

                 if (pq.top()->next)
                 {
                     LNode* tmp = pq.top()->next;
                     pq.pop();
                     pq.push(tmp);
                 }
                 else
                 {
                     pq.pop();
                 }
             }
             prev->next = nullptr;

             return head->next;
         }
     }

     ListNode* mergeKLists4(vector<ListNode*>& lists)
     {
         LNode* guard = new LNode(-1);
         priority_queue<LNode*, vector<LNode*>, Greater> pq;

         for (const auto& li : lists)
         {
             if (li)
                 pq.push(li);
         }

         LNode* tail = guard;
         while (!pq.empty())
         {
             tail->next = pq.top();
             tail = pq.top();
             if (pq.top()->next)
                 pq.push(pq.top()->next);

             pq.pop();
         }

         LNode* ans = guard->next;
         delete guard;
         return ans;
     }

 private:
     struct Greater
     {
         bool operator()(const LNode* left, const LNode* right)
         {
             return left->val > right->val;
         }
     };

     struct Less
     {
         bool operator()(const LNode* left, const LNode* right)
         {
             return left->val < right->val;
         }
     };
 };

 LNode* CreateList1()
 {
     LNode* node1 = new LNode(1);
     LNode* node2 = new LNode(4);
     LNode* node3 = new LNode(5);
     node1->next = node2;
     node2->next = node3;

     return node1;
 }

 LNode* CreateList2()
 {
     LNode* node1 = new LNode(2);
     LNode* node2 = new LNode(3);
     node1->next = node2;
     
     return node1;
 }

 void Test1(void)
 {
     vector<LNode*> lists;
     lists.push_back(CreateList1());
     lists.push_back(CreateList2());

     Solution().mergeKLists2(lists);
 }

int main()
{
    Test1();

	return 0;
}